#include "ArbolBMas.h"

ArbolBMas::ArbolBMas(){

}

ArbolBMas::ArbolBMas(string nombre_archivo, unsigned int M){
	this->primeraHoja = 0;
	this->path_file = nombre_archivo;
	this->block_Size = M*64;
	this->control_Data_Size= TAM_CONTROL_NODO;
	this->manejo_Nodos=new ManejadorDeNodos(nombre_archivo + "_Nodos.txt",this->block_Size);
	this->datos_Configuracion = new Configuracion(nombre_archivo + "_Configuracion.txt",this->block_Size);
	this->raiz = obtener_Nodo_desde_Bloque(0);
	if (this->raiz){
		this->contador_de_nodos=this->manejo_Nodos->obtener_tamanio_Archivo()/this->block_Size;
	}
	else{
		inicializar_raiz();
	}
	deserealizar_Configuracion();
}

void ArbolBMas::deserealizar_Configuracion(){
	this->datos_Configuracion->recuperar_Datos_Configuracion(this->primeraHoja);
}

void ArbolBMas::serealizar_Configuracion(){
	this->datos_Configuracion->Guardar_Datos_Configuracion(this->primeraHoja);
}


//void ArbolBMas::inicializar_archivos_de_bloques(string ruta){
//	string rutaAux = ruta + "_Nodos.txt";
//	this->manejo_Nodos=new ManejadorDeNodos(rutaAux,this->block_Size);
//
//	rutaAux = ruta + "_Configuracion.txt";
//	this->datos_Configuracion = new Configuracion(rutaAux,this->block_Size);
//
//}

void ArbolBMas::inicializar_raiz(){
	this->raiz=obtener_Hoja();
	this->raiz->idNodo=this->primeraHoja = 0;
	serealizar_Configuracion();
	(static_cast <Hoja*> (raiz))->hoja_siguiente = 0;
	this->contador_de_nodos = 1;
}

ArbolBMas::~ArbolBMas(){
	if	(raiz){
		liberar_Memoria_Nodo(raiz);
	}
	delete this->manejo_Nodos;
	delete this->datos_Configuracion;

}

Hoja* ArbolBMas::obtener_Hoja(){
	Hoja* hoja = new Hoja(this->block_Size);
	return hoja;
}

Interno* ArbolBMas::obtener_Nodo_Interno(int level){
	Interno* interno = new Interno(level,this->block_Size);
	return interno;
}

int ArbolBMas::insertar_en_hoja(Hoja* nodo_actual, RecordTermino * registro){

	quitar_FrontCoding_Hoja(&nodo_actual);
	int i = nodo_actual->contador_claves - 1;
	while (i >= 0 && registro->getTermino() < nodo_actual->claves[i]){
		nodo_actual->claves[i+1]=nodo_actual->claves[i];
		nodo_actual->registros[i+1]=nodo_actual->registros[i];
		i--;
	}

	nodo_actual->registros[i+1]= *registro;
	nodo_actual->claves[i+1]= registro->getTermino();
	nodo_actual->contador_claves++;

	if (nodo_actual->contador_claves > 1){
		aplicar_FrontCoding_Hoja(&nodo_actual);
	}

	nodo_actual->espacioOcupado += nodo_actual->registros[i+1].getTamanio() + registro->getTermino().length() + TAM_CONTROL_REGISTRO;

	if (nodo_actual->isOverflow(this->block_Size -  this->control_Data_Size)){
		return SOBREFLUJO;
	}
	else
		return EXIT_SUCCESS;
}


bool ArbolBMas::insertar(RecordTermino * registro){

	if(raiz->contador_claves != 0){
		RecordTermino * prueba = this->buscar(registro->getTermino());
		if(registro->getTermino().compare(prueba->getTermino()) == 0){
			delete prueba;
			return false;
		}
		delete prueba;
	}

	Nodo* hijo_auxiliar = NULL;
	string clave_raiz_aux;

	bool resultado = insertar_Recursivo(raiz, registro, clave_raiz_aux, &hijo_auxiliar);

	if (hijo_auxiliar){

		guardar_Nodo_en_Bloque(hijo_auxiliar);
		Interno *nueva_raiz = obtener_Nodo_Interno(raiz->nivel + 1);

		raiz->idNodo = obtener_IdNodo();

		if (this->raiz->isNodoHoja()) {
			this->primeraHoja = this->raiz->idNodo;
			serealizar_Configuracion();
		}

		guardar_Nodo_en_Bloque(raiz);

		nueva_raiz->claves[0] = clave_raiz_aux;
		nueva_raiz->hijos[0] = raiz->idNodo;
		nueva_raiz->hijos[1] = hijo_auxiliar->idNodo;
		nueva_raiz->contador_claves = 1;
		nueva_raiz->espacioOcupado += clave_raiz_aux.length() + TAM_CONTROL_REGISTRO;
		nueva_raiz->idNodo = 0;
		guardar_Nodo_en_Bloque(nueva_raiz);

		liberar_Memoria_Nodo(raiz);
		liberar_Memoria_Nodo(hijo_auxiliar);

		raiz = nueva_raiz;
	}
	guardar_Nodo_en_Bloque(raiz);
	return resultado;
}

bool ArbolBMas::insertar_Recursivo(Nodo* nodo_actual, RecordTermino* registro, string & new_key_root, Nodo** new_node){

	if (nodo_actual->isNodoHoja()){
		Hoja *hoja_actual = static_cast<Hoja*> (nodo_actual);
		int posicion = obtener_Posicion_Insercion(hoja_actual, registro->getTermino());
		int resultado_operacion=insertar_en_hoja(hoja_actual,registro);

		if (resultado_operacion==1){
			split_Hoja(hoja_actual, new_key_root, new_node);
			aplicar_FrontCoding_Hoja(&hoja_actual);
			aplicar_FrontCoding(&(*new_node));
			if (posicion >= hoja_actual->contador_claves) {
				posicion -= hoja_actual->contador_claves;
				hoja_actual = static_cast<Hoja*> (*new_node);
			}
		}
		else{
			if (hoja_actual->nivel == 0){
				aplicar_FrontCoding_Hoja(&hoja_actual);
			}
		}

		if (new_node && hoja_actual != *new_node && posicion == hoja_actual->contador_claves - 1) {
			quitar_FrontCoding_Hoja(&hoja_actual);
			new_key_root = registro->getTermino();
			aplicar_FrontCoding_Hoja(&hoja_actual);
		}
		return true;
	}
	else{

		Interno *interno_actual= static_cast<Interno*> (nodo_actual);
		string nueva_clave;
		Nodo* new_hijo = NULL;
		int posicion = obtener_Posicion_Insercion(interno_actual, registro->getTermino());
		Nodo* n_hijo = obtener_Nodo_desde_Bloque(interno_actual->hijos[posicion]);
		bool resultado = insertar_Recursivo(n_hijo, registro, nueva_clave, &new_hijo);

		if (new_hijo) {
			interno_actual->espacioOcupado += (nueva_clave).length() + TAM_CONTROL_REGISTRO;
			if (interno_actual->isOverflow( block_Size-control_Data_Size)) {
				interno_actual->espacioOcupado -= (nueva_clave).length() + TAM_CONTROL_REGISTRO;
				split_Nodo_Interno(interno_actual, new_key_root, new_node, posicion);
				if (posicion == interno_actual->contador_claves + 1 && interno_actual->contador_claves < (*new_node)->contador_claves) {
					Interno *nuevo_interno = static_cast<Interno*> (*new_node);
					interno_actual->claves[interno_actual->contador_claves] = new_key_root;
					interno_actual->hijos[interno_actual->contador_claves + 1] = nuevo_interno->hijos[0];
					interno_actual->contador_claves++;
					interno_actual->espacioOcupado += (new_key_root).length() + TAM_CONTROL_REGISTRO;
					nuevo_interno->hijos[0] = new_hijo->idNodo;
					new_key_root = nueva_clave;
					guardar_Nodo_en_Bloque(new_hijo);
					liberar_Memoria_Nodo(new_hijo);
					guardar_Nodo_en_Bloque(n_hijo);
					liberar_Memoria_Nodo(n_hijo);
					return resultado;
				}
				else {
					if (posicion >= interno_actual->contador_claves + 1) {
						posicion -= (interno_actual->contador_claves + 1);
						interno_actual= static_cast<Interno*> (*new_node);
					}
				}
			}
			interno_actual->espacioOcupado -= (nueva_clave).length() + TAM_CONTROL_REGISTRO;
			int i = interno_actual->contador_claves;
			while (i > posicion) {
				interno_actual->claves[i] = interno_actual->claves[i - 1];
				interno_actual->hijos[i + 1] = interno_actual->hijos[i];
				i--;
			}
			interno_actual->claves[posicion] = nueva_clave;
			interno_actual->hijos[posicion + 1] = new_hijo->idNodo;
			interno_actual->contador_claves++;
			interno_actual->espacioOcupado += nueva_clave.length() + TAM_CONTROL_REGISTRO;
			guardar_Nodo_en_Bloque(new_hijo);
			liberar_Memoria_Nodo(new_hijo);
		}
		guardar_Nodo_en_Bloque(n_hijo);
		liberar_Memoria_Nodo(n_hijo);
		return resultado;
	}
}


void ArbolBMas::aplicar_FrontCoding_Hoja(Hoja** n_hoja){

    (*n_hoja)->espacioOcupado -= ((*n_hoja))->registros[0].getTamanio();
    (*n_hoja)->registros[0].sacarElFrontCoding(((*n_hoja))->registros[0].getTermino(), this->path_file);
    (*n_hoja)->espacioOcupado += (*n_hoja)->registros[0].getTamanio();
	string primera = (*n_hoja)->registros[0].getTermino();

	for (int i = 1; i < (*n_hoja)->contador_claves ; i++){
		string proxima = (*n_hoja)->registros[i].getTermino();
		(*n_hoja)->espacioOcupado -= ((*n_hoja))->registros[i].getTamanio();
		(*n_hoja)->registros[i].transformarAFrontCoding(primera, this->path_file);
		(*n_hoja)->espacioOcupado += ((*n_hoja))->registros[i].getTamanio();
		primera=proxima;
	}
}

void ArbolBMas::aplicar_FrontCoding(Nodo** nodo){

	static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registros[0].getTamanio();
	static_cast<Hoja*>(*nodo)->registros[0].sacarElFrontCoding((static_cast<Hoja*>(*nodo))->registros[0].getTermino(), this->path_file);
	static_cast<Hoja*>(*nodo)->espacioOcupado += static_cast<Hoja*>(*nodo)->registros[0].getTamanio();
	string primera = static_cast<Hoja*>(*nodo)->registros[0].getTermino();

	for (int i = 1; i < static_cast<Hoja*>(*nodo)->contador_claves ; i++){
		string proxima = static_cast<Hoja*>(*nodo)->registros[i].getTermino();
		static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registros[i].getTamanio();
		static_cast<Hoja*>(*nodo)->registros[i].transformarAFrontCoding(primera, this->path_file);
		static_cast<Hoja*>(*nodo)->espacioOcupado += (static_cast<Hoja*>(*nodo))->registros[i].getTamanio();
		primera=proxima;
	}
}

int ArbolBMas::	obtener_IdNodo(){

	int idNodo;
		this->contador_de_nodos++;
		idNodo = this->contador_de_nodos-1;
	return idNodo;
}

void ArbolBMas::guardar_Nodo_en_Bloque(Nodo* nodo){
	manejo_Nodos->ActualizarArchivoNodo(nodo,nodo->getNumero());
}

Nodo* ArbolBMas::obtener_Nodo_desde_Bloque(int id_nodo){
	Nodo * nodo= manejo_Nodos->leer_Nodo(id_nodo);
	return nodo;
}

void ArbolBMas::liberar_Memoria_Nodo(Nodo* nodo){
	if (nodo->isNodoHoja()) {
		delete static_cast<Hoja*> (nodo);
	} else {
		delete static_cast<Interno*> (nodo);
	}
}

int ArbolBMas::obtener_Posicion_Insercion(Nodo *nodo, string clave) {

	if (nodo->contador_claves == 0)
		return 0;
	int inferior = 0;
	int superior = (nodo->contador_claves) - 1;

	while (inferior < superior) {
		int medio = (inferior + superior) / 2;
		if (clave.compare(nodo->claves[medio]) == -1) {
			superior = medio - 1;
		} else {
			inferior = medio + 1;
		}
	}
	if (superior < 0 || (nodo->claves[superior].compare(clave) == -1))
		superior++;

	return superior;
}

void ArbolBMas::split_Nodo_Interno(Interno* interno_actual, string & new_key_root, Nodo** new_interno, int nueva_posicion){

	int mitad = interno_actual->contador_claves / 2;

	if (nueva_posicion <= mitad && mitad > interno_actual->contador_claves - (mitad + 1)) {
		mitad--;
	}

	Interno *nuevo_interno_auxiliar = obtener_Nodo_Interno(interno_actual->nivel);
	nuevo_interno_auxiliar->idNodo = obtener_IdNodo();
	nuevo_interno_auxiliar->contador_claves = interno_actual->contador_claves - (mitad + 1);
	for (int posicion = mitad + 1; posicion < interno_actual->contador_claves; ++posicion) {
		int posicion_auxiliar = posicion - (mitad + 1);
		nuevo_interno_auxiliar->claves[posicion_auxiliar] = interno_actual->claves[posicion];
		nuevo_interno_auxiliar->hijos[posicion_auxiliar] = interno_actual->hijos[posicion];
		nuevo_interno_auxiliar->espacioOcupado += interno_actual->claves[posicion].length() + TAM_CONTROL_REGISTRO;
	}
	nuevo_interno_auxiliar->hijos[nuevo_interno_auxiliar->contador_claves] = interno_actual->hijos[interno_actual->contador_claves];
	interno_actual->contador_claves = mitad;
	interno_actual->espacioOcupado -= nuevo_interno_auxiliar->espacioOcupado;
	new_key_root = interno_actual->claves[mitad];
	*new_interno = nuevo_interno_auxiliar;
}


void ArbolBMas::split_Hoja(Hoja* n_hoja, string & clave_promovida, Nodo** nueva_hoja){

	quitar_FrontCoding_Hoja(&n_hoja);
	int mitad_en_bytes = (n_hoja->espacioOcupado) / 2;
	int bytes_hijo_izq = 0;
	int total_claves = 0;

	while (total_claves < n_hoja->contador_claves && bytes_hijo_izq < mitad_en_bytes){
		bytes_hijo_izq += n_hoja->registros[total_claves].getTamanio() + n_hoja->claves[total_claves].length() + TAM_CONTROL_REGISTRO;
		total_claves++;
		if (bytes_hijo_izq > (this->block_Size - this->control_Data_Size)) {
			total_claves--;
			bytes_hijo_izq -= (n_hoja->registros[total_claves].getTamanio() + n_hoja->claves[total_claves].length() + TAM_CONTROL_REGISTRO);
			break;
		}
	}

	Hoja *nueva_hoja_auxiliar = obtener_Hoja();
	nueva_hoja_auxiliar->idNodo = obtener_IdNodo();
	nueva_hoja_auxiliar->contador_claves = n_hoja->contador_claves - total_claves;
	nueva_hoja_auxiliar->espacioOcupado = n_hoja->espacioOcupado - bytes_hijo_izq;
	nueva_hoja_auxiliar->hoja_siguiente = n_hoja->hoja_siguiente;

	for (int posicion = total_claves; posicion < n_hoja->contador_claves; ++posicion) {
		int auxPosicion = posicion - total_claves;
		nueva_hoja_auxiliar->claves[auxPosicion] = n_hoja->claves[posicion];
		nueva_hoja_auxiliar->registros[auxPosicion] = n_hoja->registros[posicion];
	}

	n_hoja->espacioOcupado -= nueva_hoja_auxiliar->espacioOcupado;
	n_hoja->contador_claves = total_claves;
	n_hoja->hoja_siguiente = nueva_hoja_auxiliar->idNodo;
	clave_promovida = n_hoja->claves[n_hoja->contador_claves-1];
	*nueva_hoja = nueva_hoja_auxiliar;
}


void ArbolBMas::quitar_FrontCoding_Nodo(Nodo ** nodo){

	static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registros[0].getTamanio();
	static_cast<Hoja*>(*nodo)->registros[0].sacarElFrontCoding((static_cast<Hoja*>(*nodo))->registros[0].getTermino(), this->path_file);
	static_cast<Hoja*>(*nodo)->espacioOcupado += static_cast<Hoja*>(*nodo)->registros[0].getTamanio();

	for (int i = 1; i < static_cast<Hoja*>(*nodo)->contador_claves ; i++){
		static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registros[i].getTamanio();
		static_cast<Hoja*>(*nodo)->registros[i].sacarElFrontCoding(static_cast<Hoja*>(*nodo)->registros[i].getTermino(), this->path_file);
		static_cast<Hoja*>(*nodo)->espacioOcupado += (static_cast<Hoja*>(*nodo))->registros[i].getTamanio();
	}
}

RecordTermino* ArbolBMas::buscar(string clave){

	RecordTermino* buscado=buscar_Recursivo(clave,this->raiz);
	return buscado;

}

RecordTermino* ArbolBMas::buscar_Recursivo(string termino, Nodo* nodo){
	bool encontrado=false;
	int i=0;

	if (nodo->isNodoHoja()){

		Nodo* nodo_auxiliar = obtener_Nodo_desde_Bloque(nodo->idNodo);
		Hoja* hoja_actual = static_cast<Hoja*>(nodo_auxiliar);

		quitar_FrontCoding_Hoja(&hoja_actual);
		int posicion = obtener_Posicion_Insercion(hoja_actual, termino);

		while (!encontrado && hoja_actual->registros[posicion+i].getTermino().compare(termino) == 0 && ((posicion+i)< hoja_actual->contador_claves) ){
				if (hoja_actual->registros[posicion+i].getTermino().compare(termino) == 0){
					encontrado = true;
				}
				++i;
		}
		if (encontrado){
			RecordTermino* auxiliar= new RecordTermino(hoja_actual->registros[posicion+i-1].getId(), hoja_actual->registros[posicion+i-1].getTermino());
			return auxiliar;
		}
		else {
			RecordTermino* auxiliar= new RecordTermino(hoja_actual->registros[posicion+i].getId(), hoja_actual->registros[posicion+i].getTermino());
			return auxiliar;
		}
	}
	else {
		Interno *interno_actual= static_cast<Interno*> (nodo);

		int posicion = obtener_Posicion_Insercion(interno_actual, termino);
		Nodo* n_hijo = obtener_Nodo_desde_Bloque(interno_actual->hijos[posicion]);

		RecordTermino* auxiliar = buscar_Recursivo(termino,n_hijo);
		return auxiliar;

	}

}


void ArbolBMas::quitar_FrontCoding_Hoja(Hoja ** nodo){

    (*nodo)->espacioOcupado -= ((*nodo))->registros[0].getTamanio();
    (*nodo)->registros[0].sacarElFrontCoding(((*nodo))->registros[0].getTermino(), this->path_file);
    (*nodo)->espacioOcupado += (*nodo)->registros[0].getTamanio();

	for (int i = 1; i < (*nodo)->contador_claves ; i++){
		(*nodo)->espacioOcupado -= ((*nodo))->registros[i].getTamanio();
		(*nodo)->registros[i].sacarElFrontCoding((*nodo)->registros[i].getTermino(), this->path_file);
		(*nodo)->espacioOcupado += ((*nodo))->registros[i].getTamanio();
	}
}


void ArbolBMas::MostrarArbol (){
	ofstream file;
	string ruta = this->path_file + ".txt";
	file.open(ruta.c_str(), ios_base::out);
	file << ".|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|" << endl << endl;
	file << "			            ARBOL B+ de "; file << this->path_file << "                  " << endl << endl;
	file << ".|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|" << endl << endl;
	if (raiz){
		file << "					TAMANIO NODO:  " << this->block_Size << endl;
		file << "					PRIMER HOJA:  " << primeraHoja << endl;
		file << "____________________________________________________________________________" << endl << endl;
	}
	if (this->raiz){
		toString(this->raiz,1, file);
	}
	file.flush();
	file.close();
}


void ArbolBMas::EscribirListadoOrdenado (){
	ofstream file_list;
	string ruta = this->path_file +"_listado"+ ".txt";
	file_list.open(ruta.c_str(), ios_base::out);
	Nodo* nodo_total = obtener_Nodo_desde_Bloque(this->primeraHoja);

		toString_listado(nodo_total, file_list);

		liberar_Memoria_Nodo(nodo_total);
		file_list.flush();
		file_list.close();
}

void ArbolBMas::toString_listado(Nodo* nodo, ofstream& file_list){

	Hoja *hoja = static_cast<Hoja*> (nodo);
	quitar_FrontCoding_Hoja(&hoja);

	for (int i=0; i < hoja->contador_claves; i++){
		file_list << hoja->registros[i].getTermino() << endl;
	}
	if (hoja->hoja_siguiente != 0){
		Nodo* nodo_aux = obtener_Nodo_desde_Bloque(hoja->hoja_siguiente);
		toString_listado(nodo_aux, file_list);
	}

}

void ArbolBMas::toString(Nodo* nodoAmostrar, int tab, ofstream& file){

	if(nodoAmostrar){
			if (nodoAmostrar->isNodoHoja()) {
				Hoja *nodo = static_cast<Hoja*> (nodoAmostrar);
				for(int i=0 ; i<tab ; i++) file << "  ";
					file   << "|" << nodo->idNodo <<  "|" << nodo->nivel << "|" << nodo->contador_claves
					 << "(" << nodo->hoja_siguiente << ")    " << endl;

				for(int i=0 ; i<tab ; i++) file << "  ";
				for (int posicion = 0; posicion < nodo->contador_claves; ++posicion){
					file << "(";
					string clave = (nodo->registros[posicion].getTermino());
					file << clave;
					file << ",";
					file << nodo->registros[posicion].getId();
					file << ",";
					file << nodo->registros[posicion].getZero();
					file << ")";
				}
				file << endl;
			} else {
				Interno *nodoInt= static_cast<Interno*> (nodoAmostrar);
				file << endl;
				for(int i=0; i<tab ; i++)
					file << " ";
				file << "|" << nodoInt->idNodo << "|" << nodoInt->nivel << "|" << nodoInt->contador_claves<< " (";
				for (int posicion = 0; posicion <= nodoInt->contador_claves; ++posicion) {
					if (posicion < nodoInt->contador_claves) {
						string clave = nodoInt->claves[posicion];
						file << clave;
						if (posicion == nodoInt->contador_claves-1){
							file << ")" << endl;
						}else{
							file << "," ;
						}
					}
				}
				int * hijos;
				Nodo *hijo;
				for (int posicion = 0; posicion <= nodoInt->contador_claves; ++posicion) {

					hijos = nodoInt->getHijos();
					hijo = obtener_Nodo_desde_Bloque(hijos[posicion]);
					toString(hijo, tab+2, file);
					if (hijo)
						liberar_Memoria_Nodo(hijo);
				}
				file << endl;
			}
		}
}

